470. Super palindromes

The palindrome is a string with a length greater than one character that reads the same both from right to left and left to right. A superpalindrome is a string that can be represented as the concatenation of one or more palindromes.

You are given a string s. Find the number of substrings in s that are superpalindromes.

Input. The string s that consists of a sequence of lowercase Latin letters with a length from 1 to 1000, without spaces.

Output. Print a single integer – the number of substrings of the string s that are superpalindromes.

Sample input	Sample output
abacdc	3

SOLUTION

dynamic programming - palindrome

Algorithm analysis

Let s be the input string. The substring s_i … s_j is a palindrome, if one of the following conditions is satisfyed:

· i ≥ j (the substring is empty or consists of a single character);

· s_i = s_j and the substring s_i+1…s_j-1 is a palindrome;

Let the function IsPal(i, j) returns 1, if s_i…s_j is a palindrome, and 0 otherwise. The values of IsPal(i, j) are stored in the array pal[i][j].

A string is a superpalindrome if it can be represented as the concatenation of one or more palindromes. For example, the following strings are superpalindromes:

Let dp[i][j] = 1, if the substring s_i…s_j (i < j) is a superpalindrome and dp[i][j] = 0 otherwise. Iterate over all pairs (i, j) for 0 ≤ i < j < n and if the substring s_i…s_j is a palindrome, then it is also a super palindrome, so we set dp[i][j] = 1. Note that dp[i][j] = 0 for i ≥ j. A word consisting of a single letter is not considered a palindrome, so as a special case, we have dp[i][i] = 0.

For each pair (i, j), iterate over all possible values of k (i < k < j – 1) and if s_i…s_k and s_k+1…s_j are superpalindromes (and consist of more than one character due to the restriction on k), then s_i…s_j is also a super palindrome.

It remains to count the number of pairs (i, j) where i < j and dp[i][j] = 1. This number is the answer.

Example

For the given example – the string “abacdc”, there are 3 substrings that are superpalindromes:

There are 5 substrings for “aaaba” that are superpalindromes:

Algorithm realization

Declare the arrays.

#define MAX 1010

char s[MAX];

int dp[MAX][MAX];

int pal[MAX][MAX];

The function IsPal(i, j) checks if the substring s_i…s_j is a palindrome. The substring s_i…s_j is a palindrome if s_i = s_j and s_i+1…s_j-1 is also a palindrome. The values of IsPal(i, j) are stored in the array pal[i][j].

int IsPal(int i, int j)

{

if (i >= j) return pal[i][j] = 1;

if (pal[i][j] != -1) return pal[i][j];

return pal[i][j] = (s[i] == s[j]) && IsPal(i+1,j-1);

}

The main part of the program. Read the input string.

gets(s); n = strlen(s);

memset(dp,0,sizeof(dp));

memset(pal,-1,sizeof(pal));

Iterate over all pairs (i, i + len) in increasing order of interval lengths.

for(len = 1; len < n; len++)

for(i = 0; i + len < n; i++)

{

j = i + len;

Substring s_i…s_j contains more than one character. If it is a palindrome, then it is also a super palindrome.

if (IsPal(i,j))

{

dp[i][j] = 1;

continue;

}

If s_i…s_k and s_k+1…s_j are superpalindromes, then s_i…s_j is also a superpalindrome.

for(k = i + 1; k < j - 1; k++)

if(dp[i][k] && dp[k + 1][j])

{

dp[i][j] = 1;

break;

}

}

Count the number of superpalindromes.

res = 0;

for(i = 0; i < n; i++)

for(j = i+1; j < n; j++)

res += dp[i][j];

Print the answer.

printf("%d\n",res);

Algorithm realization – recursive

Declare the input string s and arrays.

#define MAX 1010

string s;

int dp[MAX][MAX], pal[MAX][MAX];

The function IsPal(i, j) checks if the substring s_i…s_j is a palindrome. The substring s_i…s_j is a palindrome if s_i = s_j and s_i+1…s_j-1 is also a palindrome. The values of IsPal(i, j) are stored in the array pal[i][j].

int IsPal(int i, int j)

{

if (i >= j) return pal[i][j] = 1;

if (pal[i][j] != -1) return pal[i][j];

return pal[i][j] = (s[i] == s[j]) && IsPal(i+1,j-1);

}

The function f(i, j) returns 1 if s_i…s_j is a superpalindrome.

int f(int i, int j)

{

A superpalindrome must contain more than one character.

if (i == j) return dp[i][j] = 0;

If the value of f(i, j) is already computed, return its value.

if (dp[i][j] != -1) return dp[i][j];

If the substring s_i…s_j (i < j) is a palindrome, then it is also a superpalindrome.

if (IsPal(i,j)) return dp[i][j] = 1;

If s_i…s_k (i < k) is a palindrome, and s_k+1…s_j (k + 1 < j) is a superpalindrome, then s_i…s_j is a superpalindrome.

for(int k = i + 1; k < j - 1; k++)

if(IsPal(i,k) && f(k + 1,j)) return dp[i][j] = 1;

If none of the above conditions is satisfied, then s_i…s_j is not a superpalindrome.

return dp[i][j] = 0;

}

The main part of the program. Read the input string s and compute its length n.

cin >> s; n = s.size();

Initialize the dp and pal arrays.

memset(dp,-1,sizeof(dp));

memset(pal,-1,sizeof(pal));

In the variable res, count the number of superpalindromes.

res = 0;

for(i = 0; i < n; i++)

for(j = i + 1; j < n; j++)

res += f(i,j);

Print the answer.

cout << res << endl;

Java realization

import java.util.*;

public class Main

{

static String s;

static int dp[][], pal[][];

static int IsPal(int i, int j)

{

if (i >= j) return pal[i][j] = 1;

if (pal[i][j] != -1) return pal[i][j];

if (s.charAt(i) == s.charAt(j) && IsPal(i+1,j-1) == 1) pal[i][j] = 1;

else pal[i][j] = 0;

return pal[i][j];

}

static int f(int i, int j)

{

if (i == j) return dp[i][j] = 0;

if (dp[i][j] != -1) return dp[i][j];

if (IsPal(i,j) == 1) return dp[i][j] = 1;

for(int k = i + 1; k < j - 1; k++)

if(IsPal(i,k) == 1 && f(k + 1,j) == 1) return dp[i][j] = 1;

return dp[i][j] = 0;

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

s = con.nextLine();

int n = s.length();

dp = new int[n][n];

pal = new int[n][n];

for(int i = 0; i < n; i++)

for(int j = 0; j < n; j++)

{

dp[i][j] = -1;

pal[i][j] = -1;

}

int res = 0;

for(int i = 0; i < n; i++)

for(int j = i+1; j < n; j++)

res += f(i,j);

System.out.println(res);

con.close();

}

}